
#include <stack>
#include <vector>
#include <string>
#include <queue>
using namespace std;
//有效的括号
class Solution {
public:
    bool isValid(string s) 
    {
        stack<char>st;
        for(int i=0;i<s.size();i++)
        {
            if(st.empty())
            {
                st.push(s[i]);
                continue;
            }
            if(s[i]==')' && st.top()=='(') st.pop();
            else if(s[i]==']' && st.top()=='[' ) st.pop();
            else if(s[i]=='}' && st.top()=='{') st.pop();
            else 
            {
                st.push(s[i]);
            }
        }
        return st.empty();
    }
};

//用队列实现栈
class MyStack {
public:
    MyStack() {

    }
    
    void push(int x) 
    {
        q.push(x);
    }
    
    int pop() 
    {
        while(q.size()>1)
        {
            copy_q.push(q.front());
            q.pop();
        }
        int pop=q.front();
        q=copy_q;
        while(!copy_q.empty())
        {
            copy_q.pop();
        }
        return pop;
    }
    
    int top() 
    {
        copy_q=q;
        int top=0;
        while(!copy_q.empty())
        {
            top=copy_q.front();
            copy_q.pop();
        }
        return top;
    }
    
    bool empty() 
    {
        return q.empty();
    }
private:
    queue<int> q;
    queue<int> copy_q;
};

//用栈实现队列
class MyQueue {
public:
    MyQueue() {

    }
    
    void push(int x) 
    {
        inst.push(x);

    }
    
    int pop() 
    {
        if(outst.empty())
        {
            while(!inst.empty())
            {
                outst.push(inst.top());
                inst.pop();
            }
        }
        int pop=outst.top();
        outst.pop();
        return pop;

    }
    
    int peek() 
    {
        if(outst.empty())
        {
            while(!inst.empty())
            {
                outst.push(inst.top());
                inst.pop();
            }
        }
        int peek=outst.top();
        return peek;
    }
    
    bool empty() 
    {
        return inst.empty() && outst.empty();
    }
private:
    stack<int> inst;
    stack<int> outst;

};

//设计循环队列
class MyCircularQueue {
private:
    vector<int> _v;
    int _front;//头指针
    int _rear;//尾指针
    int _capacity;
public:
    MyCircularQueue(int k) 
    {
        _capacity=k+1;
        _v.reserve(_capacity);
        _front=_rear=0;
    }
    
    bool enQueue(int value) 
    {
        if(isFull()) return false;
        _v[_rear]=value;
        _rear=(_rear+1)%_capacity;
        return true;
    }
    
    bool deQueue() 
    {
        if(isEmpty()) return false;
        _front=(_front+1)%_capacity;
        return true;

    }
    
    int Front() 
    {
        if(isEmpty()) return -1;
        return _v[_front];
    }
    
    int Rear() 
    {
        if(isEmpty()) return -1;
        return _v[(_rear-1+_capacity)%_capacity];
    }
    
    bool isEmpty() 
    {
        return _rear==_front;
    }
    
    bool isFull() 
    {
        if( (_rear+1)%_capacity==_front)
        return true;
        else 
        return false;
    }
};